#include <bits/stdc++.h>

#define fi first
#define se second
#define eb emplace_back
#define ep emplace
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

const int N = 1e5 + 10;
const ll inf = 1e12;
const int M = 510 * 510 * 4;

int n;
int a[510][510];

namespace F {
	const ll INF = 1e18;
	int h[N], now[N], cnt, S, T;
	bool vis[N];
	ll maxflow, cost, dis[N];
	struct edge { int v, w; ll c; int nxt; } e[M << 1];
	void reset() { cnt = 1; rep(i, 0, T) now[i] = h[i] = 0; S = T = 0; maxflow = cost = 0; cnt = 1;}
	void tlink(int x, int y, int w, ll c) { e[++cnt] = (edge){ y, w, c, h[x] }; h[x] = cnt; }
	void link(int x, int y, int w, ll c) { tlink(x, y, w, c), tlink(y, x, 0, -c); }
	void setst(int s, int t) { S = s, T = t; }
	bool bfs() {
		queue < int > q; q.ep(S); rep(i, 0, T) dis[i] = INF, vis[i] = 0;
		dis[S] = 0, now[S] = h[S], vis[S] = 1;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = h[x], y; i; i = e[i].nxt) {
				if(e[i].w && dis[y = e[i].v] > dis[x] + e[i].c) {
					dis[y] = dis[x] + e[i].c; now[y] = h[y];
					if(!vis[y]) vis[y] = 1, q.ep(y);
				}
			}
			vis[x] = 0;
		} return dis[T] < INF;
	}
	int dinic(int x, int flow, ll c) {
		if(x == T) return maxflow += flow, cost += c * flow, flow;
		int ret = flow; vis[x] = 1;
		for(int i = now[x], y; i && ret; i = e[i].nxt) {
			now[x] = i;
			if(e[i].w && dis[y = e[i].v] == dis[x] + e[i].c && !vis[y]) {
				int k = dinic(y, min(ret, e[i].w), c + e[i].c);
				e[i].w -= k, e[i ^ 1].w += k, ret -= k;
			} vis[x] = 0; 
		} return flow - ret;
	}
	void runit() { while(bfs() && dis[T] < 0) dinic(S, 0x3f3f3f3f, 0); }
}

void solve() {
	scanf("%d", &n); rep(i, 1, n) rep(j, 1, n)  scanf("%d", &a[i][j]);
	F :: reset(), F :: setst(0, n * 2 + 1);
	ll ans = F :: INF;
	rep(i, 1, n) F :: link(0, i, 1, -inf), F :: link(0, i, n, 0);
	//rep(i, 1, n) F :: link(i + n, n * 2 + 1, 1, -inf), F :: link(i + n, n * 2 + 1, n, 0);
	rep(i, 1, n) F :: link(i + n, n * 2 + 1, n, 0);
	rep(i, 1, n) rep(j, 1, n) {
		F :: link(i, j + n, 1, a[i][j]);
	} F :: runit();
	chkmin(ans, F :: cost + n * inf);
	//printf("%lld\n", F :: cost + n * 2 * inf);
	
	F :: reset(), F :: setst(0, n * 2 + 1);
	//rep(i, 1, n) F :: link(0, i, 1, -inf), F :: link(0, i, n, 0);
	rep(i, 1, n) F :: link(0, i, n, 0);
	rep(i, 1, n) F :: link(i + n, n * 2 + 1, 1, -inf), F :: link(i + n, n * 2 + 1, n, 0);
	//rep(i, 1, n) F :: link(i + n, n * 2 + 1, n, 0);
	rep(i, 1, n) rep(j, 1, n) {
		F :: link(i, j + n, 1, a[i][j]);
	} F :: runit();
	chkmin(ans, F :: cost + n * inf);
	
	printf("%lld\n", ans);
}
int main() {
#ifdef YJR_2333_TEST
	freopen("1.in", "r", stdin);
#endif
	//ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T; scanf("%d", &T);
	while(T--) solve();
}
